\documentclass[E:/GsjzTle/main/main.tex]{subfiles}


\begin{document}

\begin{itemize}
\item
  \(n\) 个点的无向图，起初无任何边
\item

    为 \(u，v\) 加一条边（保证 \(u,v\) 之间始终只有一条边）

\item

    删除 \(u,v\) 之间的边（保证合法）

\item

    判断 \(u,v\) 是否联通

\item
  \(n≤10^5, m≤2\times 10^5\)
\end{itemize}

离线。记录每条边出现的时间和结束的时间，然后套线段树时间分治

\begin{lstlisting}
#include<bits/stdc++.h>
#define rep(i , a , b) for (int i = a ; i <= b ; i ++)
#define fi first
#define se second 
#define pb push_back
using namespace std;

const int N = 3e5 + 10;
typedef pair<int , int> pii;

int n , m , far[N] , size[N];
map<pair<int , int> , int>mp;
vector<pair<pii , int>>Q[N];
int find(int x)
{
	if(x == far[x]) return x;
	return find(far[x]); // 不能用路径压缩！ 
}
void Union(int x , int y , stack<pii>&st)
{
	int tx = find(x) , ty = find(y);
	if(tx != ty) 
	{
		if(size[tx] > size[ty]) swap(tx , ty);
		st.push(make_pair(tx , ty));
		far[tx] = ty;
		size[ty] += size[tx];
	}
}
void Redo(stack<pii>&st)
{
	while(!st.empty())
	{
		pii u = st.top();
		st.pop();
		far[u.fi] = u.fi;
		size[u.se] -= size[u.fi];
	}
}
struct Tree{ 
	int l , r;
	vector<pair<int , int>>vec;
}tree[N << 2];
void build(int l , int r , int rt)
{
	tree[rt].l = l , tree[rt].r = r;
	tree[rt].vec.clear();
	if(l == r) return ;
	int mid = l + r >> 1;
	build(l , mid , rt << 1);
	build(mid + 1 , r , rt << 1 | 1);
}
void update_range(int L , int R , int rt , pair<int , int>p)
{
	int l = tree[rt].l , r = tree[rt].r;
	if(L <= l && r <= R)
	{
		tree[rt].vec.pb(p);
		return ;
	}
	int mid = l + r >> 1;
	if(L <= mid) update_range(L , R , rt << 1 , p);
	if(R >  mid) update_range(L , R , rt << 1 | 1 , p);
}
void query(int rt)
{
	int l = tree[rt].l , r = tree[rt].r; 
	stack<pii>st;
	for(auto i : tree[rt].vec) Union(i.fi , i.se , st);
	if(l == r)
	{
		if(Q[l].size())
		{
			int tx = find(Q[l][0].fi.fi) , ty = find(Q[l][0].fi.se);
			if(tx == ty) Q[l][0].se = true;
			else Q[l][0].se = false;
		}
	} 
	else
	{
		int mid = l + r >> 1;
		query(rt << 1);
		query(rt << 1 | 1);
	}
	Redo(st);
}
signed main()
{
	cin >> n >> m;
	rep(i , 1 , n) far[i] = i , size[i] = 1;
	build(1 , m , 1);
	rep(i , 1 , m)
	{
		string op;
		int u , v;
		cin >> op >> u >> v;
		if(u > v) swap(u , v);
		if(op[0] == 'Q') Q[i].pb(make_pair(make_pair(u , v) , false));
		else if(op[0] == 'C') 
		{
			if(mp.find(make_pair(u , v)) == mp.end()) mp[make_pair(u , v)] = i; 
		}
		else 
		{
			update_range(mp[make_pair(u , v)] , i , 1 , make_pair(u , v));
			mp.erase(mp.find(make_pair(u , v)));
		}
	}
	for(auto i : mp) update_range(i.se , m , 1 , i.fi);
	query(1);
	rep(i , 1 , m) if(Q[i].size()) Q[i][0].se ? cout << "Yes\n" : cout << "No\n";
	return 0;
}
\end{lstlisting}

\end{document}
